package test6;

import java.util.ArrayList;
import java.util.Scanner;

public class Solution1 { //prim算法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入结点个数：");
        int num = sc.nextInt();
        GraphAdList graphAdList = new GraphAdList(num);
        for (int i = 0; i < num; i++) {
            System.out.println("请输入与第" + i + "个点相邻点的个数：");
            int node = sc.nextInt();
            System.out.println("请分别输入该点及其相邻点的名称和到该点的权值：");
            for (int j = 0; j <= node; j++) {
                String value = sc.next();
                int weight = sc.nextInt();
                graphAdList.addNode(value, weight, i);
            }
        }
        graphAdList.showGraphAdList();
        System.out.println("请输入开始结点：");
        String start = sc.next();
        graphAdList.prim(start);
    }
}

class Node{
    String value;
    Node next;
    int weight;
    public Node(){}
}

class AdList{
    Node firstNode;
    public AdList(){}

    public void add(String value, int weight){
        if (firstNode == null){
            firstNode = new Node();
            firstNode.value = value;
            firstNode.weight = weight;
        }else {
            Node p = firstNode;
            while (p.next != null){
                p = p.next;
            }
            p.next = new Node();
            p.next.value = value;
            p.next.weight = weight;
        }
    }

    public void showList(){
        System.out.print(firstNode.value + "(" + firstNode.weight + ")");
        Node p = firstNode;
        while(p.next != null){
            System.out.print("->" + p.next.value + "(" + p.next.weight + ")");
            p = p.next;
        }

    }
}

class GraphAdList{
    int size;
    AdList[] adLists;

    public void prim(String value){
        int pos = getPos(value);
        int nextPos;
        //标记结点是否访问过
        int[] visited = new int[size];
        int[] min = new int[size];
        //存储包含在最小生成树中的结点
        ArrayList tree = new ArrayList();
        for (int i = 0; i < size; i++) {
            min[i] = 9999;
        }
        visited[pos] = 1;
        min[pos] = 0;
        tree.add(pos);
        int minWeight;
        int MST = 0;
        System.out.print("连通图最小边权路径为：" + value);
        int node = 0; //记录离最小生成树最近的点
        for (int i = 1; i < size; i++) {
            minWeight = 9999;
            for (Object o : tree) {
                Node p = adLists[(int) o].firstNode;
                while (p.next != null) {
                    nextPos = getPos(p.next.value);
                    if (visited[nextPos] == 0 && p.next.weight <= min[nextPos]) {
                        min[nextPos] = p.next.weight;
                        if (minWeight > p.next.weight) {
                            minWeight = p.next.weight;
                            node = nextPos;
                        }
                    }
                    p = p.next;
                }
            }
            if (visited[node] == 0){//未访问过的结点加入更新距离
                System.out.print("->" + adLists[node].firstNode.value);
                visited[node] = 1;
                min[node] = 0;
                tree.add(node);
                if (minWeight < 9999){
                    MST += minWeight;
                }
                Node p = adLists[node].firstNode;
                while (p.next != null){ //更新最短路径
                    nextPos = getPos(p.next.value);
                    if (visited[nextPos] == 0 && p.next.weight < min[nextPos]){
                        min[nextPos] = p.next.weight;
                    }
                    p = p.next;
                }
            }
        }
        System.out.println();
        System.out.println("连通图最小边权总和：" + MST);
    }

    public int getPos(String value){
        for (int i = 0; i < size; i++) {
            if (adLists[i].firstNode.value.equalsIgnoreCase(value)){
                return i;
            }
        }
        return -1;
    }

    public GraphAdList(int size) {
        this.size = size;
        adLists = new AdList[size];
        for (int i = 0; i < size; i++) {
            adLists[i] = new AdList();
        }
    }

    public void addNode(String value, int weight, int pos){
        adLists[pos].add(value, weight);
    }

    public void showGraphAdList(){
        for (int i = 0; i < size; i++) {
            adLists[i].showList();
            System.out.println();
        }
    }
}